template <typename T>

// todo 添加一个构造函数传入指定长度
class MyVector{

private:
    T* data;		// 静态数组
    int size;       // 存储数组中的元素个数
    int capacity;   // 存储数组中可以容纳的最大的元素个数

    // 复杂度为 O(n)
    void resize(int newCapacity){
		// 新开辟空间能容纳所有元素
        assert(newCapacity >= size);
		// 将旧数组数据复制到新数组
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ )
            newData[i] = data[i];
        delete[] data;

        data = newData;		// data指针指向新开辟空间
        capacity = newCapacity;
    }

public:
    MyVector():MyVector(10){}

	MyVector(int cap): size(0), capacity(cap){
		data = new T[capacity];
	}
    ~MyVector(){

        delete[] data;
    }

    // 平均复杂度为 O(1)		数组最后添加元素
    void push_back(T e){
		// 数组越界
        if(size == capacity)
            resize(2 * capacity);

        data[size++] = e;
    }

    // 平均复杂度为 O(1)      删除数组中最后一个元素
    T pop_back(){
		// 通过减少数组值个数，让最后一个元素不在合法范围
        assert(size > 0);
		T ret = data[size - 1];     	//  先存储，方便后面返回
		size --;
		/**
		 * 在size达到静态数组最大容量的1/4时才进行resize
		 * resize的容量是当前最大容量的1/2
		 * 防止复杂度的震荡
		 */
		 if(size == capacity / 4)
			resize(capacity / 2);
		 
		 return ret;
    }	

};
